home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / pd / pathalias / mapit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-03  |  15.4 KB  |  681 lines
  1. /* Smail SCCS ID: @(#)pd/pathalias/mapit.c    1.2 %G 00:43:35 */
  2. /* pathalias -- by steve bellovin, as told to peter honeyman */
  3. #ifndef lint
  4. static char    *sccsid = "@(#)mapit.c    9.13 88/06/12";
  5. #endif
  6.  
  7. #include "def.h"
  8.  
  9. #define chkheap(i)    /* void */
  10. #define chkgap()    /* int */
  11.  
  12. #define trprint(stream, n) \
  13.     fprintf((stream), (n)->n_flag & NTERMINAL ? "<%s>" : "%s", (n)->n_name)
  14.  
  15. /* exports */
  16. /* invariant while mapping: Nheap < Hashpart */
  17. long Hashpart;        /* start of unreached nodes */
  18. long Nheap;        /* end of heap */
  19. long NumNcopy, Nlink, NumLcopy;
  20.  
  21. void mapit();
  22.  
  23. /* imports */
  24. extern long Nheap, Hashpart, Tabsize, Tcount;
  25. extern int Tflag, Vflag;
  26. extern node **Table, *Home;
  27. extern char *Linkout, *Graphout;
  28.  
  29. extern void freelink(), resetnodes(), printit(), dumpgraph();
  30. extern void showlinks(), die();
  31. extern long pack(), allocation();
  32. extern link *newlink(), *addlink();
  33. extern int maptrace(), tiebreaker();
  34. extern node *ncopy();
  35.  
  36.  
  37. /* privates */
  38. static long    Heaphighwater;
  39. static link    **Heap;
  40.  
  41. STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
  42. STATIC void setheapbits(), mtracereport(), heapchildren(), otracereport();
  43. STATIC link *min_node();
  44. STATIC int dehash(), skiplink(), skipterminalalias();
  45. STATIC Cost costof();
  46. STATIC node *mappedcopy();
  47.  
  48. /* transform the graph to a shortest-path tree by marking tree edges */
  49. void
  50. mapit()
  51. {    register node *n;
  52.     register link *l;
  53.  
  54.     vprintf(stderr, "*** mapping\ttcount = %ld\n", Tcount);
  55.     Tflag = Tflag && Vflag;        /* tracing here only if verbose */
  56.     /* re-use the hash table space for the heap */
  57.     Heap = (link **) Table;
  58.     Hashpart = pack(0L, Tabsize - 1);
  59.  
  60.     /* expunge penalties from -a option and make circular copy lists */
  61.     resetnodes();
  62.  
  63.     if (Linkout && *Linkout)    /* dump cheapest links */
  64.         showlinks();
  65.     if (Graphout && *Graphout)    /* dump the edge list */
  66.         dumpgraph();
  67.  
  68.     /* insert Home to get things started */
  69.     l = newlink();        /* link to get things started */
  70.     l->l_to = Home;
  71.     (void) dehash(Home);
  72.     insert(l);
  73.  
  74.     /* main mapping loop */
  75.     do {
  76.         Heaphighwater = Nheap;
  77.         while ((l = min_node()) != 0) {
  78.             l->l_flag |= LTREE;
  79.             n = l->l_to;
  80.             if (n->n_flag & MAPPED)        /* sanity check */
  81.                 die("mapped node in heap");
  82.             if (Tflag && maptrace(n, n))
  83.                 otracereport(n);    /* tracing */
  84.             chkheap(1); chkgap();        /* debugging */
  85.             n->n_flag |= MAPPED;
  86.             heapchildren(n);    /* add children to heap */
  87.         }
  88.         vprintf(stderr, "heap hiwat %d\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), NumNcopy, Nlink, NumLcopy);
  89.  
  90.         if (Nheap != 0)        /* sanity check */
  91.             die("null entry in heap");
  92.  
  93.         /*
  94.          * add back links from unreachable hosts to reachable
  95.          * neighbors, then remap.  asymptotically, this is
  96.          * quadratic; in practice, this is done once or twice,
  97.          * when n is small.
  98.          */
  99.         backlinks();
  100.     } while (Nheap > 0);
  101.  
  102.     if (Hashpart < Tabsize) {
  103.         int foundone = 0;
  104.  
  105.         for ( ; Hashpart < Tabsize; Hashpart++) {
  106.             if (Table[Hashpart]->n_flag & ISPRIVATE)
  107.                 continue;
  108.             if (foundone++ == 0)
  109.                 fputs("You can't get there from here:\n", stderr);
  110.             putc('\t', stderr);
  111.             trprint(stderr, Table[Hashpart]);
  112.             putc('\n', stderr);
  113.         }
  114.     }
  115. }
  116.  
  117. STATIC void
  118. heapchildren(n)
  119.     register node *n;
  120. {    register link *l;
  121.     register node *next;
  122.     register int mtrace;
  123.     register Cost cost;
  124.  
  125.     for (l = n->n_link; l; l = l->l_next) {
  126.  
  127.         next = l->l_to;        /* neighboring node */
  128.         mtrace = Tflag && maptrace(n, next);
  129.  
  130.         if (l->l_flag & LTREE)
  131.             continue;
  132.  
  133.         if (l->l_flag & LTERMINAL)
  134.             l->l_to = next = ncopy(n, l);
  135.  
  136.         if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS))
  137.             if (skipterminalalias(n, next))
  138.                 continue;
  139.             else
  140.                 l->l_to = next = ncopy(n, l);
  141.  
  142.         if (next->n_flag & MAPPED) {
  143.             if (mtrace)
  144.                 mtracereport(n, l, "-\talready mapped");
  145.             continue;
  146.         }
  147.         cost = costof(n, l);
  148.  
  149.         if (skiplink(l, n, cost, mtrace))
  150.             continue;
  151.  
  152.         /*
  153.          * put this link in the heap and restore the
  154.          * heap property.
  155.          */
  156.         if (mtrace) {
  157.             if (next->n_parent)
  158.                 mtracereport(next->n_parent, l, "*\tdrop");
  159.             mtracereport(n, l, "+\tadd");
  160.         }
  161.         next->n_parent = n;
  162.         if (dehash(next) == 0) {  /* first time */
  163.             next->n_cost = cost;
  164.             insert(l);      /* insert at end */
  165.             heapup(l);
  166.         } else {
  167.             /* replace inferior path */
  168.             Heap[next->n_tloc] = l;
  169.             if (cost > next->n_cost) {
  170.                 /* increase cost (gateway) */
  171.                 next->n_cost = cost;
  172.                 heapdown(l);
  173.             } else if (cost < next->n_cost) {
  174.                 /* cheaper route */
  175.                 next->n_cost = cost;
  176.  
  177.                 heapup(l);
  178.             }
  179.         }
  180.         setheapbits(l);
  181.         chkheap(1);
  182.  
  183.     }
  184. }
  185.  
  186. /* 
  187.  * bizarro special case.  this merits comment.
  188.  * 
  189.  * n is a terminal node just sucked out of the heap, next is an alias
  190.  * for n.  because n is terminal, it must have one or more "copies."
  191.  * if next is one of those copies, don't put next in the heap.
  192.  *
  193.  * does that clear things up?
  194.  */
  195. STATIC int
  196. skipterminalalias(n, next)
  197.     node *n, *next;
  198. {
  199.  
  200.     while (n->n_flag & NALIAS) {
  201.         n = n->n_parent;
  202.         if (ALTEREGO(n, next))
  203.             return 1;
  204.     }
  205.     return 0;
  206. }
  207.  
  208. /*
  209.  * return 1 if we definitely don't want want this link in the
  210.  * shortest path tree, 0 if we might want it, i.e., best so far.
  211.  *
  212.  * if tracing is turned on, report only if this node is being skipped.
  213.  */
  214. STATIC int
  215. skiplink(l, parent, cost, trace)
  216.     link *l;        /* new link to this node */
  217.     node *parent;        /* (potential) new parent of this node */
  218.     register Cost cost;    /* new cost to this node */
  219.     int trace;        /* trace this link? */
  220. {    register node *n;    /* this node */
  221.     register link *lheap;        /* old link to this node */
  222.  
  223.     n = l->l_to;
  224.  
  225.     /* first time we've reached this node? */
  226.     if (n->n_tloc >= Hashpart)
  227.         return 0;
  228.  
  229.     lheap = Heap[n->n_tloc];
  230.  
  231.     /* examine links to nets that require gateways */
  232.     if (GATEWAYED(n)) {
  233.         /* if exactly one is a gateway, use it */
  234.         if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
  235.             if (trace)
  236.                 mtracereport(parent, l, "-\told gateway");
  237.             return 1;    /* old is gateway */
  238.         }
  239.         if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
  240.             return 0;    /* new is gateway */
  241.  
  242.         /* no gateway or both gateways;  resolve in standard way ... */
  243.     }
  244.  
  245.     /* examine dup link (sanity check) */
  246.     if (n->n_parent == parent && (DEADLINK(lheap) || DEADLINK(l)))
  247.         die("dup dead link");
  248.  
  249.     /*  examine cost */
  250.     if (cost < n->n_cost)
  251.         return 0;
  252.     if (cost > n->n_cost) {
  253.         if (trace)
  254.             mtracereport(parent, l, "-\tcheaper");
  255.         return 1;
  256.     }
  257.  
  258.     /* all other things being equal, ask the oracle */
  259.     if (tiebreaker(n, parent)) {
  260.         if (trace)
  261.             mtracereport(parent, l, "-\ttiebreaker");
  262.         return 1;
  263.     }
  264.     return 0;
  265. }
  266.  
  267. /* compute cost to l->l_to via parent */
  268. STATIC Cost
  269. costof(prev, l)
  270.     register node *prev;
  271.     register link *l;
  272. {    register node *next;
  273.     register Cost cost;
  274.  
  275.     if (l->l_flag & LALIAS)
  276.         return prev->n_cost;    /* by definition */
  277.  
  278.     next = l->l_to;
  279.     cost = prev->n_cost + l->l_cost;    /* basic cost */
  280.  
  281.     /*
  282.      * heuristics:
  283.      *    charge for a dead link.
  284.      *    charge for getting past a terminal host
  285.      *        or getting out of a dead host.
  286.      *    charge for getting into a gatewayed net (except at a gateway).
  287.      *    discourage mixing of syntax (when prev is a host).
  288.      *
  289.      * life was simpler when pathalias computed true shortest paths.
  290.      */
  291.     if (DEADLINK(l))
  292.         cost += INF;                /* dead link */
  293.     if (DEADHOST(prev))
  294.         cost += INF;                /* dead parent */
  295.     if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))
  296.         cost += INF;                /* not gateway */
  297.     if (!ISANET(prev)) {
  298.         if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
  299.          || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
  300.             cost += INF;            /* mixed syntax */
  301.     }
  302.  
  303.     return cost;
  304. }
  305.  
  306. /* binary heap implementation of priority queue */
  307.  
  308. STATIC void
  309. insert(l)
  310.     link *l;
  311. {    register node *n;
  312.  
  313.     n = l->l_to;
  314.     if (n->n_flag & MAPPED)
  315.         die("insert mapped node");
  316.  
  317.     Heap[n->n_tloc] = 0;
  318.     if (Heap[Nheap+1] != 0)
  319.         die("heap error in insert");
  320.     if (Nheap++ == 0) {
  321.         Heap[1] = l;
  322.         n->n_tloc = 1;
  323.         return;
  324.     }
  325.     if (Vflag && Nheap > Heaphighwater)
  326.         Heaphighwater = Nheap;    /* diagnostics */
  327.  
  328.     /* insert at the end.  caller must heapup(l). */
  329.     Heap[Nheap] = l;
  330.     n->n_tloc = Nheap;
  331. }
  332.  
  333. /*
  334.  * "percolate" up the heap by exchanging with the parent.  as in
  335.  * min_node(), give tiebreaker() a chance to produce better, stable
  336.  * routes by moving nets and domains close to the root, nets closer
  337.  * than domains.
  338.  *
  339.  * i know this seems obscure, but it's harmless and cheap.  trust me.
  340.  */
  341. STATIC void
  342. heapup(l)
  343.     link *l;
  344. {    register long cindx, pindx;    /* child, parent indices */
  345.     register Cost cost;
  346.     register node *child, *parent;
  347.  
  348.     child = l->l_to;
  349.  
  350.     cost = child->n_cost;
  351.     for (cindx = child->n_tloc; cindx > 1; cindx = pindx) {
  352.         pindx = cindx / 2;
  353.         if (Heap[pindx] == 0)    /* sanity check */
  354.             die("impossible error in heapup");
  355.         parent = Heap[pindx]->l_to;
  356.         if (cost > parent->n_cost)
  357.             return;
  358.  
  359.         /* net/domain heuristic */
  360.         if (cost == parent->n_cost) {
  361.             if (!ISANET(child))
  362.                 return;
  363.             if (!ISADOMAIN(parent))
  364.                 return;
  365.             if (ISADOMAIN(child))
  366.                 return;
  367.         }
  368.         heapswap(cindx, pindx);
  369.     }
  370. }
  371.  
  372. /* extract min (== Heap[1]) from heap */
  373. STATIC link    *
  374. min_node()
  375. {    link *rval, *lastlink;
  376.     register link **rheap;
  377.  
  378.     if (Nheap == 0)
  379.         return 0;
  380.  
  381.     rheap = Heap;        /* in register -- heavily used */
  382.     rval = rheap[1];    /* return this one */
  383.  
  384.     /* move last entry into root and reheap */
  385.     lastlink = rheap[Nheap];
  386.     rheap[Nheap] = 0;
  387.  
  388.     if (--Nheap) {
  389.         rheap[1] = lastlink;
  390.         lastlink->l_to->n_tloc = 1;
  391.         heapdown(lastlink);    /* restore heap property */
  392.     }
  393.  
  394.     return rval;
  395. }
  396.  
  397. /*
  398.  * swap Heap[i] with smaller child, iteratively down the tree.
  399.  *
  400.  * given the opportunity, attempt to place nets and domains
  401.  * near the root.  this helps tiebreaker() shun domain routes.
  402.  */
  403.  
  404. STATIC void
  405. heapdown(l)
  406.     link *l;
  407. {    register long pindx, cindx;
  408.     register link **rheap = Heap;    /* in register -- heavily used */
  409.     node *child, *rchild, *parent;
  410.  
  411.     pindx = l->l_to->n_tloc;
  412.     parent = rheap[pindx]->l_to;    /* invariant */
  413.     for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
  414.         /* pick lhs or rhs child */
  415.         child = rheap[cindx]->l_to;
  416.         if (cindx < Nheap) {
  417.             /* compare with rhs child */
  418.             rchild = rheap[cindx+1]->l_to;
  419.             /*
  420.              * use rhs child if smaller than lhs child.
  421.              * if equal, use rhs if net or domain.
  422.              */
  423.             if (child->n_cost > rchild->n_cost) {
  424.                 child = rchild;
  425.                 cindx++;
  426.             } else if (child->n_cost == rchild->n_cost)
  427.                 if (ISANET(rchild)) {
  428.                     child = rchild;
  429.                     cindx++;
  430.                 }
  431.         }
  432.  
  433.         /* child is the candidate for swapping */
  434.         if (parent->n_cost < child->n_cost)
  435.             break;
  436.  
  437.         /*
  438.          * heuristics:
  439.          *    move nets/domains up
  440.          *    move nets above domains
  441.          */
  442.         if (parent->n_cost == child->n_cost) {
  443.             if (!ISANET(child))
  444.                 break;
  445.             if (ISANET(parent) && ISADOMAIN(child))
  446.                 break;
  447.         }
  448.  
  449.         heapswap(pindx, cindx);
  450.     }
  451. }
  452.  
  453. /* exchange Heap[i] and Heap[j] pointers */
  454. STATIC void
  455. heapswap(i, j)
  456.     long i, j;
  457. {    register link *temp, **rheap;
  458.  
  459.     rheap = Heap;    /* heavily used -- put in register */
  460.     temp = rheap[i];
  461.     rheap[i] = rheap[j];
  462.     rheap[j] = temp;
  463.     rheap[j]->l_to->n_tloc = j;
  464.     rheap[i]->l_to->n_tloc = i;
  465. }
  466.  
  467. /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
  468. STATIC int
  469. dehash(n)
  470.     register node *n;
  471. {
  472.     if (n->n_tloc < Hashpart)
  473.         return 1;
  474.  
  475.     /* swap with entry in Table[Hashpart] */
  476.     Table[Hashpart]->n_tloc = n->n_tloc;
  477.     Table[n->n_tloc] = Table[Hashpart];
  478.     Table[Hashpart] = n;
  479.  
  480.     n->n_tloc = Hashpart++;
  481.     return 0;
  482. }
  483.  
  484. /*
  485.  * everything reachable has been mapped.  what to do about any
  486.  * unreachable hosts?  the sensible thing to do is to dump them on
  487.  * stderr and be done with it.  unfortunately, there are hundreds of
  488.  * such hosts in the usenet maps.  so we take the low road: for each
  489.  * unreachable host, we add a back link from its cheapest mapped child,
  490.  * in the faint that a reverse path works.
  491.  *
  492.  * beats me why people want their error output in their map databases.
  493.  */
  494. STATIC void
  495. backlinks()
  496. {    register link *l;
  497.     register node *n, *child;
  498.     node *nomap;
  499.     long i;
  500.  
  501.     /* hosts from Hashpart to Tabsize are unreachable */
  502.     for (i = Hashpart; i < Tabsize; i++) {
  503.         nomap = Table[i];
  504.         /* if a copy has been mapped, we're ok */
  505.         if (nomap->n_copy != nomap) {
  506.             dehash(nomap);
  507.             Table[nomap->n_tloc] = 0;
  508.             nomap->n_tloc = 0;
  509.             continue;
  510.         }
  511.  
  512.         /* TODO: simplify this */        
  513.         /* add back link from minimal cost child */
  514.         child = 0;
  515.         for (l = nomap->n_link; l; l = l->l_next) {
  516.             n = l->l_to;
  517.             /* never ever ever crawl out of a domain */
  518.             if (ISADOMAIN(n))
  519.                 continue;
  520.             if ((n = mappedcopy(n)) == 0)
  521.                 continue;
  522.             if (child == 0) {
  523.                 child = n;
  524.                 continue;
  525.             }
  526.             if (n->n_cost > child->n_cost)
  527.                 continue;
  528.             if (n->n_cost == child->n_cost) {
  529.                 nomap->n_parent = child; /* for tiebreaker */
  530.                 if (tiebreaker(nomap, n))
  531.                     continue;
  532.             }
  533.             child = n;
  534.         }
  535.         if (child == 0)
  536.             continue;
  537.         (void) dehash(nomap);
  538.         l = addlink(child, nomap, INF, DEFNET, DEFDIR);    /* INF cost */
  539.         nomap->n_parent = child;
  540.         nomap->n_cost = costof(child, l);
  541.         insert(l);
  542.         heapup(l);
  543.         if (Vflag > 1)
  544.             fprintf(stderr, "backlink: %s <- %s\n", nomap->n_name, child->n_name);
  545.     }
  546.     vprintf(stderr, "%d backlinks\n", Nheap);
  547. }
  548.  
  549. /* find a mapped copy of n if it exists */
  550. STATIC node *
  551. mappedcopy(n)
  552.     register node *n;
  553. {    register node *ncp;
  554.  
  555.     if (n->n_flag & MAPPED)
  556.         return n;
  557.     for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
  558.         if (ncp->n_flag & MAPPED)
  559.             return ncp;
  560.     return 0;
  561. }
  562.  
  563. /*
  564.  * l has just been added or changed in the heap,
  565.  * so reset the state bits for l->l_to.
  566.  */
  567. STATIC void
  568. setheapbits(l)
  569.     register link *l;
  570. {    register node *n;
  571.     register node *parent;
  572.  
  573.     n = l->l_to;
  574.     parent = n->n_parent;
  575.     n->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);    /* reset */
  576.  
  577.     /* record whether link is an alias */
  578.     if (l->l_flag & LALIAS) {
  579.         n->n_flag |= NALIAS;
  580.         /* TERMINALity is inherited by the alias */
  581.         if (parent->n_flag & NTERMINAL)
  582.             n->n_flag |= NTERMINAL;
  583.     }
  584.  
  585.     /* set left/right bits */
  586.     if (NETDIR(l) == LLEFT || (parent->n_flag & HASLEFT))
  587.         n->n_flag |= HASLEFT;
  588.     if (NETDIR(l) == LRIGHT || (parent->n_flag & HASRIGHT))
  589.         n->n_flag |= HASRIGHT;
  590. }
  591.  
  592. STATIC void
  593. mtracereport(from, l, excuse)
  594.     node *from;
  595.     link *l;
  596.     char *excuse;
  597. {    node *to = l->l_to;
  598.  
  599.     fprintf(stderr, "%-16s ", excuse);
  600.     trprint(stderr, from);
  601.     fputs(" -> ", stderr);
  602.     trprint(stderr, to);
  603.     fprintf(stderr, " (%ld, %ld, %ld) ", from->n_cost, l->l_cost, to->n_cost);
  604.     if (to->n_parent) {
  605.         trprint(stderr, to->n_parent);
  606.         fprintf(stderr, " (%ld)", to->n_parent->n_cost);
  607.     }
  608.     putc('\n', stderr);
  609. }
  610.  
  611. STATIC void
  612. otracereport(n)
  613.     node *n;
  614. {
  615.     if (n->n_parent)
  616.         trprint(stderr, n->n_parent);
  617.     else
  618.         fputs("[root]", stderr);
  619.     fputs(" -> ", stderr);
  620.     trprint(stderr, n);
  621.     fputs(" mapped\n", stderr);
  622. }
  623.     
  624. #if 0
  625. /* extremely time consuming, exhaustive check of heap sanity. */
  626. chkheap(i)
  627. {    int lhs, rhs;
  628.  
  629.     lhs = i * 2;
  630.     rhs = lhs + 1;
  631.  
  632.     if (lhs <= Nheap) {
  633.         if (Heap[i]->l_to->n_cost > Heap[lhs]->l_to->n_cost)
  634.             die("chkheap failure on lhs");
  635.         chkheap(lhs);
  636.     }
  637.     if (rhs <= Nheap) {
  638.         if (Heap[i]->l_to->n_cost > Heap[rhs]->l_to->n_cost)
  639.             die("chkheap failure on rhs");
  640.         chkheap(rhs);
  641.     }
  642. #if 00
  643.     /* this hasn't been used for years */
  644.     for (i = 1; i < Nheap; i++) {
  645.         link *l;
  646.  
  647.         vprintf(stderr, "%5d %-16s", i, Heap[i]->l_to->n_name);
  648.         if ((l = Heap[i]->l_to->n_link) != 0) do {
  649.             vprintf(stderr, "%-16s", l->l_to->n_name);
  650.         } while ((l = l->l_next) != 0);
  651.         vprintf(stderr, "\n");
  652.     }
  653.     for (i = Hashpart; i < Tabsize; i++) {
  654.         link *l;
  655.         node *n;
  656.  
  657.         vprintf(stderr, "%5d %-16s", i, Table[i]->n_name);
  658.         if ((l = Table[i]->n_link) != 0) do {
  659.             vprintf(stderr, "%-16s", l->l_to->n_name);
  660.         } while ((l = l->l_next) != 0);
  661.         vprintf(stderr, "\n");
  662.     }
  663. #endif /*00*/
  664.         
  665. }
  666. #endif /*0*/
  667.  
  668. /* this isn't much use */
  669. #if 0
  670. STATIC int
  671. chkgap()
  672. {    static int gap = -1;
  673.     int newgap;
  674.  
  675.     newgap = Hashpart - Nheap;
  676.     if (gap == -1 || newgap < gap)
  677.         gap = newgap;
  678.     return gap;
  679. }
  680. #endif /*0*/
  681.